The present invention relates to a semiconductor signal processing apparatus, and particularly to a semiconductor signal processing apparatus having the function of executing an arithmetic operation using a semiconductor memory in the inside thereof. More particularly, the present invention relates to a semiconductor signal processing apparatus which detects a match/mismatch between an input data pattern and a registered data pattern.
In data communication via a communication network, data aiming at an unauthorized access is communicated oftentimes. To prevent such an unauthorized access, various security measures are taken in various places such as a network site or a router. As one of such security measures, there is a system called Network Intrusion Detection System (NIDS). The NIDS monitors a data packet flowing over a network, and senses an attack to a processing system (such as a server or a personal computer) such as malicious intrusion or a computer virus. Information on this sensed attack is stored in a log, and an alarm is issued to play a role in maintaining the security of the system.
As a core component of such a NIDS, a character-string pattern retrieving device exists which senses an attack packet (data pattern) in a payload transferred via a network. An example of such a pattern retrieving device is shown in Non-Patent Document 1 (F. Yu, R. H. Katz, T. V. Lakshman, “Gigabit Rate Packet Pattern-Matching Using TCAM,” 12th IEEE ICNP' 04 Digest of Technical Papers, pp. 174-pp. 183, 2004). The sensing of this attack packet is performed using a pattern matching method. In Non-Patent Document 1, pattern detection is performed using a ternary content addressable memory or ternary CAM (TCAM). The TCAM is obtained by extending the function of a content addressable memory (CAM) such that retrieval data is given as an input, and a memory address holding the same content as that of the retrieval data is outputted. The TCAM not only allows match/mismatch determination for “1” and “0” bits to be made, but also allows ternary determination to be made which tolerates a “don't care” state in which, whether a bit of interest is either “1” or “0”, a data bit match is assumed.
The pattern retrieval shown in Non-Patent Document 1 is executed as follows. That is, patterns to be retrieved (registered patterns) are stored in advance in individual entries in the TCAM according to a predetermined priority scheme. A first w-byte pattern of an inputted string (character string) is compared in parallel with the patterns to be retrieved that are mapped to the individual entries in the TCAM. If there is a matching entry, the corresponding address (index) is reported. When the retrieval to each of the entries is completed, the input string is shifted by 1 byte, and a retrieving operation for the next w-byte pattern is executed. The retrieving operation is repeated. Using the address (record) of the matching entry, a table is referenced, and a matched data pattern is identified.
In general, as described in Non-Patent Document 1 and also in Non-Patent Document 2 (S. Dharmarpuricar et. al., “Fast and Scalable Pattern Matching for Network Intrusion Detection System,” IEEE, Journal on Selected Areas in Communications, Vol. 24, No. 10, October 2006, pp. 1781-1792), the length of a string retrieval pattern used in the NIDS or the like is distributed in a range of ten to several thousands of bytes, and there are several hundreds of pattern lengths as candidates for the pattern length. The pattern length has a non-uniform distribution in which retrieval patterns of not more than 20 bytes account for about nearly 80% of all the retrieval patterns (see FIG. 4 of Non-Patent Document 2).
In Non-Patent Document 1, when the length of a to-be-retrieved pattern to be mapped is shorter than a TCAM width determined by the length of a match line (bit width of an entry), information of the “don't care” state is mapped to make the pattern length equal to the TCAM width. In this manner, a variable-length string pattern required in the NIDS is mapped to each of the entries, and retrieval is executed.
Non-Patent-Document 2 discloses a structure aiming at performing retrieval of data of an arbitrary pattern length. Specifically, in Non-Patent Document 2, retrieval is performed as a pre-process using a Bloom filter, and then match retrieval is performed using a hash table. The retrieval is performed by shifting an input data pattern by one byte at a time. As a retrieval algorithm, an algorithm in which pattern retrieval is performed in a tree-like configuration is used.
Also, a structure which performs data retrieval when the bit width of retrieval data is variable is shown in each of Patent Document 1 (Japanese Unexamined Patent Publication No. Hei 09 (1997)-161488), Patent Document 2 (Japanese Unexamined Patent Publication No. Hei 02 (1990)-308499), and Patent Document 3 (Japanese Unexamined Patent Publication No. Hei 11 (1999)-273363).
In the structure shown in Patent Document 1 (Japanese Unexamined Patent Publication No. Hei 09 (1997)-161488), a memory array is divided into a plurality of blocks, and comparators are disposed correspondingly to the individual blocks. Each of the blocks includes a plurality of entries, and the entries are selected in parallel in the plurality of blocks. The bit widths of the entries are fixed, but mask bits are provided among the bits mapped to the entries, thereby allowing the bit width of data to be retrieved to be changed, and changing the bit width of inputted retrieval data in response thereto. By contrast, in Non-Patent Document 1, when the length of a to-be-retrieved pattern to be mapped is shorter than a TCAM width determined by the length of a match line (bit width of an entry), information of the “don't care” state is mapped to make the pattern length equal to the TCAM width. In this manner, a variable-length string pattern required in the NIDS is mapped to each of the entries, and retrieval is executed. In each of the blocks, the retrieval is performed successively on a per-entry basis.
In the structure shown in Patent Document 2 (Japanese Unexamined Patent Publication No. Hei 02 (1990)-308499) also, a memory array is divided into a plurality of cell blocks, and the results of retrieval in the individual cell blocks are combined to produce a final retrieval result. In the structure shown in Patent Document 2, a configuration which allows the bit width of retrieval data to be changed is not shown. In Patent Document 2, only a binary CAM (BCAM) cell structure is shown as a memory cell structure.
In the structure shown in Patent Document 3 (Japanese Unexamined Patent Publication No. Hei 11 (1999)-273363), a plurality of CAM arrays are provided in descending order from top to bottom, and input data is divided and given according to the position of each of the CAM arrays. At the same addresses in the plurality of CAM arrays, data patterns related to the same pattern are stored. During retrieval, when a match is retrieved in a lower-order CAM array, retrieval is performed in a higher-order CAM array using the matching address in the lower-order CAM array and, when the matching address in the higher-order CAM array matches the matching address in the lower-order CAM array, it is determined that retrieval data matches a stored data pattern. When the matching address in the lower-order CAM array does not match the matching address in the higher-order CAM array, retrieval is performed in the lower-order CAM array using the matching address in the higher-order CAM array, and a match/mismatch is determined in the lower-order CAM array. Patent Document 3 described above intends to perform retrieval of a data pattern of an arbitrary bit width by providing the plurality of CAM arrays according to the lengths of retrieval data patterns.